HashMap与LinkedHashMap

发表于 | 分类于 | 阅读次数

1. 简介

在日常开发中我们经常会批量操作数据，因此很多高级语言除了提供数组，还给我们提供很多高级的、抽象的数据类型来让我们处理批量数据时得心应手。由于这些轮子对于程序的性能是比较关键的轮子，因此很多语言都内置的提供了比较精致的实现。在java中，这种实现被称为集合框架。集合框架包含的接口、类十分丰富，而且功能强大，因此理解并熟悉java集合框架，对于写出正确高效的程序是十分有必要的。java集合框架中包含两个重要的类LinkedHashMap与HashMap，它们常常被用于按key-value存储、操作数据，对于常见的操作都是常数的时间复杂度，因此被广泛使用，虽然这两个类的作用类似，但是他们的实现和使用场景稍微不同。

2. 二者的区别

HashMap与LinkedHashMap都实现了Map接口，二者的存储形式都是采用bucket加链表的形式来进行存储的。二者的主要区别:

  • HashMap由于是按照key的hash值映射到对应的bucket中，无法保证遍历HashMap时的顺序是预期的顺序
  • LinkedHashMap在HashMap的基础上加以改进，却可以保证遍历的顺序要么是插入item的顺序或者LRU访问的顺序

这是因为LinkedHashMap维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的。

如果选择LRU访问的顺序，LinkedHashMap对于访问过的item会将其移动到双链表的末尾，这样保证最近访问过的item是处于链表末端，因此较老其不经常使用的item会处于链表前端。这个特性恰好符合LRU的思想，因此LinkedHashMap可以用来实现LRU Cache。Android提供的SDK的LruCache类便是利用LinkedHashMap实现了基于Lru规则的缓存功能。

另外可以发现在java8中HashMap和LinkedHashMap有了改动，据说在某些Hash碰撞严重时，性能也不会太差。java8之前的Map实现的问题是当出现某个bucket的后面的链表太长了，也就是说发生hash冲突的item太多了，这样会导致访问操作退化到了O(n)。

java8的改进便是当bucket的链表长度大于阈值的时候，会将链表重新组织为一颗红黑树，这样在hash碰撞严重的时候性能还是可以保证到log(n).改进前后的示意图如下所示：

这里写图片描述

在使用LinkedHashMap和HashMap的时候应该注意Key的hash值是怎么取得，如果不同的key经常出现相同的hash值，则会频繁出现冲突，降低性能。

同时，由于改进后的HashMap会在某个bucket后的链表长度超过某个阈值时，重新将连边组织为一颗红黑树，因此在java8上的key最好实现Comparable接口来保证key是可以通过compareTo进行比较的，因为这样会简化建立红黑树的判断流程，提高效率。当然如果不实现Comparable接口的话，也会有相应的方法保证hash值冲突的item形成一颗平衡的红黑树。

3. 源码阅读

此处选取几个关键的地方进行源码分析：

  1. 对于HashMap重点关注这几个方法
1
final void treeifyBin(Node<K,V>[] tab, int hash)
1
public V put(K key, V value)
1
final void treeify(Node<K,V>[] tab)
1
static int tieBreakOrder(Object a, Object b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
//通过hash找到对应的桶，如果桶空则直接新建一个链表节点置于桶中并成为链表头
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {//桶不为空，则从桶内存放的链表头开始查找
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))//运气好的话，在链表头就找到了，注意此处key的匹配规则，首先是 == 匹配，然后再是调用equals方法匹配
        e = p;
    else if (p instanceof TreeNode)//如果该桶内存放的不再是链表，而是一颗树，则按树的规则去执行。
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {//按链表顺序查找，并记录链表的节点数目
            if ((e = p.next) == null) {//如果查找到了链表尾，认为匹配到key,则新建一个节点
                p.next = newNode(hash, key, value, null);
                //java8改进的地方！！！！如果桶内链表的长度大于了阈值则树形化该链表
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))//匹配到一个存在的item
                break;
            p = e;
        }
    }
    //如果成功匹配了key，则此次put操作仅仅是修改value而没有插入新的节点
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);//访问元素e的回调，注意比较LinkedHashMap在此处的实现。
        return oldValue;
    }
}
++modCount;
if (++size > threshold)//如果真个hashmap的长度超过了阈值，就说明可能会出现严重的hash冲突此时就应该resize()，rehash。
    resize();
afterNodeInsertion(evict);//插入元素e的回调，注意比较LinkedHashMap在此处的实现。
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果Hash表的桶数小于可以树形化的阈值，则只是扩大桶数，进行再Hash
//我估计在设计的时候权衡了重建一颗红黑树和再Hash的cost，当桶的数量很少的时候，再hash划算一些
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
    TreeNode<K,V> hd = null, tl = null;
    do {
        //从链表头hd,将每一个节点转化为一个树节点且继续保持链表的顺序
        TreeNode<K,V> p = replacementTreeNode(e, null);
        if (tl == null)
            hd = p;
        else {
            p.prev = tl;
            tl.next = p;
        }
        tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
        hd.treeify(tab);//最终树形化链表在这里完成
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/**
 * Forms tree of the nodes linked from this node.
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //以当前对象作为root，开始构建一颗红黑树
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;//当前树节点x包含的key
            int h = x.hash;//当前树节x点的hash值
            Class<?> kc = null;//x节点包含的key的类
            //从红黑树的根节点开始寻找合适的插入的位置，然后再平衡该树。
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //正常来讲，由于HashMap是树形化一个桶内的链表，因此
                //每个链表的节点的hashCode()返回的值应该是一样的。
                //因此这里两个分支(ph = p.hash) > h 和 ph < h应该都不会被执行
                //这里会直接进入分支3进行判断
                if ((ph = p.hash) > h)//分支1
                    dir = -1;
                else if (ph < h)//分支2
                    dir = 1;
                   //分支3 当两个节点的hash值相等的时候（事实上绝大部分都是这样的情况）
                    //则反射判断x节点的key的类是否是实现了Comparable接口，如果实现了则利用compareTo方法进行比较判断，从而决定插入的位置；
                    //如果没有实现Comparable接口或者实现了Comparable接口但是compareTo比较的结果还是一致，则利用tieBreakOrder来决定大小。
                    //因为红黑树的节点都要有大小区分的，不能出现大小相同的节点，因此无论采用哪种量化方式，一定得比较个大小出来。
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);//当俩节点hashCode返回值相等且没有实现comparable接口，在这种尴尬僵持的局面，就需要调用tieBreakOrder方法
                //来一较高低了。因此java8中对于HashMap的文档中建议Key要实现Comparable接口，这样此处就不会进入到如此尴尬僵持的局面，会提高些许性能，毕竟后面
                //打破僵局是需要付出代价的

                TreeNode<K,V> xp = p;
                //直到走到叶节点，则进行插入
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;//如果该节点x比父亲节点p小，则作为节点p的左孩子
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);//红黑树都有的操作，插入节点后需要进行调整以继续保证红黑树的性质
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);//保证桶内存放的是红黑树的根节点root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * Forms tree of the nodes linked from this node.
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //以当前对象作为root，开始构建一颗红黑树
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;//当前树节点x包含的key
            int h = x.hash;//当前树节x点的hash值
            Class<?> kc = null;//x节点包含的key的类
            //从红黑树的根节点开始寻找合适的插入的位置，然后再平衡该树。
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //正常来讲，由于HashMap是树形化一个桶内的链表，因此
                //每个链表的节点的hashCode()返回的值应该是一样的。
                //因此这里两个分支(ph = p.hash) > h 和 ph < h应该都不会被执行
                //这里会直接进入分支3进行判断
                if ((ph = p.hash) > h)//分支1
                    dir = -1;
                else if (ph < h)//分支2
                    dir = 1;
                   //分支3 当两个节点的hash值相等的时候（事实上绝大部分都是这样的情况）
                    //则反射判断x节点的key的类是否是实现了Comparable接口，如果实现了则利用compareTo方法进行比较判断，从而决定插入的位置；
                    //如果没有实现Comparable接口或者实现了Comparable接口但是compareTo比较的结果还是一致，则利用tieBreakOrder来决定大小。
                    //因为红黑树的节点都要有大小区分的，不能出现大小相同的节点，因此无论采用哪种量化方式，一定得比较个大小出来。
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);//当俩节点hashCode返回值相等且没有实现comparable接口，在这种尴尬僵持的局面，就需要调用tieBreakOrder方法
                //来一较高低了。因此java8中对于HashMap的文档中建议Key要实现Comparable接口，这样此处就不会进入到如此尴尬僵持的局面，会提高些许性能，毕竟后面
                //打破僵局是需要付出代价的

                TreeNode<K,V> xp = p;
                //直到走到叶节点，则进行插入
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;//如果该节点x比父亲节点p小，则作为节点p的左孩子
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);//红黑树都有的操作，插入节点后需要进行调整以继续保证红黑树的性质
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);//保证桶内存放的是红黑树的根节点root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * Tie-breaking utility for ordering insertions when equal
 * hashCodes and non-comparable. We don't require a total
 * order, just a consistent insertion rule to maintain
 * equivalence across rebalancings. Tie-breaking further than
 * necessary simplifies testing a bit.
 */
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)//先利用两对象的类名的大小比较，若仍然陷入僵局，则调用
        //System.identityHashCode()的方法该方法会返回对象唯一的真实的hash值无论对象的类是否重写了hashCode方法
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

以上部分简要的分析了HashMap的改进处的源码。

  1. 对于LinkedHashMap,主要阅读分析其如何保证迭代的顺序、具有LRU的性质
    LinkedHashMap是HashMap的子类，只是稍加改造便使得其具有链表的顺序性质。
    1
    2

    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;//维护的双向链表的
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;//维护的双向链表的表尾

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;//是访问顺序还是插入顺序

主要关注以下几个方法：

1
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e)
1
private void linkNodeLast(LinkedHashMap.Entry<K,V> p)
1
2

void afterNodeAccess(Node<K,V> e)
1
2

void afterNodeInsertion(boolean evict)
1
2

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
1
2
3
4
5
6
7
8
//这个方法是HashMap的hook方法，只是简单的扩展了HashMap的Node类，就完成了LinkedHashMap的大部分功能
//不得不说类的设计很巧妙
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
    new LinkedHashMap.Entry<K,V>(hash, key, value, e);//将节点e
linkNodeLast(p);//将该Entry链接到LinkedHashMap维护的双向链表的表尾
return p;
}
1
2
3
4
5
6
7
8
9
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
    super(hash, key, value, next);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;//tail是维护的双链表的表尾
tail = p;
//接下就是简单的链表链接操作
if (last == null)
    head = p;
else {
    p.before = last;
    last.after = p;
}
}

由于LinkedHashMap没有重写put方法，因此它复用了HashMap的put方法，只是简单重写了hook方法newNode。因此put方法不用分析了。到此应该就可以去看迭代器的实现了，讲道理的话应该是按照双向链表的顺序来迭代的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;

LinkedHashIterator() {
    next = head;//head存放的是双向链表的表头
    expectedModCount = modCount;
    current = null;
}

public final boolean hasNext() {
    return next != null;
}

final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after;//依次迭代
    return e;
}
}

自此已经大致清楚了LinkedHashMap是如何简单的改造了HashMap而拥有了顺序的迭代。

LinkedHashMap不仅仅遍历是有序的，而且还可以选择是何种顺序，是插入顺序还是访问顺序。

acceeOrder的定义了遍历是何种顺序，该值默认是false,若想为true,需要显示的指定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//如果是访问顺序，则将节点e放在链表尾部
if (accessOrder && (last = tail) != e) {
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a != null)
        a.before = b;
    else
        last = b;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
    tail = p;
    ++modCount;
}
}

这样无论是put还是get操作都会导致该元素e会被放在链表尾部。这样链表表头部分的元素的访问时间就相对久远了，这个特性就恰恰比较符合LRU的思想。因此当LinkiedHashMap的元素个数超过一定的阈值时（因为缓存的容量是有限的），就需要删除某些缓存item了。在LinkedHashMap中就有这样的CallBack来完成这个目的。

1
2
3
4
5
6
7
8
9

void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//如果该LinkedHashMap允许删除老元素，则移除老元素
if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
}
}

LinkedHashMap默认是不移除老元素，因此要实现Lru需要重写该方法。

1
2
3
4

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}

通常会这么重写

1
2
3
4
5
private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
}

可以看出来LinkedHashMap只是稍微加以改进，就具备了额外的功能。这种类的设计十分精致，值得借鉴。
HashMap预留了几个关键的hook方法给扩展类(此处是LinkedHashMap)，例如newNode(),afterAccess() afterInsertion()等。这样就是策略和机制分离了，便于扩展类添加更丰富的功能。当然我们也可以按照需要扩展HashMap,从而改变其某些行为。

但是HashMap类中的TreeNode怎么会去继承子类LinkedHashMap的Entry，难道仅仅是为了少些几行代码？我觉得这个设计不是很好。毕竟父类不应该去获取子类的某些信息，有点本末倒置。

1
2
3
4
5
6
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

4. Best Practices

  • 在使用HashMap时应该尽量保证key的hashCode返回值分布均匀性；在java8上使用时key应该尽量实现comparable接口。

    • LinkedHashMap和HashMap性能的比较:在基本的put get remove操作，两者的性能几乎相近，由于LinkedHashMap维护着一个双向链表，因此性能可能稍微差一点点。但是在迭代遍历的时候，因为LinkedHashMap遍历的所有的插入的元素，而HashMap是遍历的整个HashMap（包括一些空桶），因此LinkedHashMap的性能稍微优于HashMap。

    • LinkedHashMap可以保持任意的Map的顺序信息，就像这样使用：

    1
    2
    3
    4
    5

    void foo(Map m) {
            Map copy = new LinkedHashMap(m);
            ...
      }